package syf.recursion;

public class MiGong {
    private static int[][] ary=walld(8,7);
    public static void main(String[] args) {
//        walld(8,7);
        displayMap(ary);
        go(ary,1,1);
        displayMap(ary);
    }

    /**
     * 定义一个8行7列的迷宫
     * 边界都是墙 墙定义为1
     *
     * 1	1	1	1	1	1	1
     * 1	0	0	0	0	0	1
     * 1	0	0	0	0	0	1
     * 1	1	1	0	0	0	1
     * 1	0	0	0	0	0	1
     * 1	0	0	0	0	0	1
     * 1	0	0	0	0	0	1
     * 1	1	1	1	1	1	1
     *
     *
     */
    public static int[][] walld(int rank,int line){
        int[][] ary=new int[rank][line];
        for (int i=0;i<rank;i++){
            for (int j=0;j<line;j++){
                //第一行和最后一行
                if (i==0||i==rank-1){
                    ary[i][j]=1;
                }
                //第一列和最后一列
                if (j==0||j==line-1){
                    ary[i][j]=1;
                }
                if (i==3&&(j==1||j==2)){
                    ary[i][j]=1;
                }
            }
        }
//        ary[1][2]=1;
//        ary[2][2]=1;
        return ary;
    }

    /**
     *
     * @param map 地图
     * @param startRank 开始位置行
     * @param startLine 开始位置列
     * @return 找到路了返回真否则返回假
     * 约定：当为0表示没有走过，1表示墙，2表示此路走通，3表示此路已经走过了，但是走不通
     * 走迷宫时确定策略：下-右-上-左，如果该点走不通再回溯
     */
    public static boolean go(int[][] map,int startRank,int startLine){
        if (map[4][1]==2) {
            System.out.println("已经走通");
            return true;
        }
        else {
            if (map[startRank][startLine] == 0) {
                //策略：下-右-上-左
                map[startRank][startLine] = 2;
                //下
                if (go(map, startRank + 1, startLine)) {
                    return true;
                }//右
                else if (go(map, startRank, startLine + 1)) {
                    return true;
                }//上
                else if (go(map, startRank - 1, startLine)) {
                    return true;
                }
                //左
                else if (go(map, startRank, startLine - 1)) {
                    return true;
                } else {
                    map[startRank][startLine] = 3;//这个点走不通
                    return false;
                }
            }
            else {
                return false;
            }
        }
    }
    public static void displayMap(int[][] ary){
        for (int[] x:ary){
            for (int y:x){
                System.out.print(y+"\t");
            }
            System.out.println();
        }
        System.out.println("======================");
    }
}

